# 二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
#  例如，下面的二进制手表读取 "3:25" 。
#
#  给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
#  小时不会以零开头：
#  例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。
#
#  分钟必须由两位数组成，可能会以零开头：
#  例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。
#
#  示例 1：
# 输入：turnedOn = 1
# 输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
#
#  示例 2：
# 输入：turnedOn = 9
# 输出：[]
from typing import List


class Solution:
    def readBinaryWatch2(self, turnedOn: int) -> List[str]:
        """
        枚举所有的时间

        :param turnedOn:
        :return:
        """
        if turnedOn >= 9:
            return []
        res = []
        # 分别枚举所有的时针、分针
        for hour in range(12):
            for minute in range(60):
                if bin(hour).count('1') + bin(minute).count('1') == turnedOn:
                    res.append(f'{hour}:{minute:02d}')

        # 枚举二进制(总共10位二进制数，可以表示 0 - 2^10 - 1),每个数字可以代表一种时间
        # for i in range(1 << 10):
        #     if bin(i).count('1') == turnedOn and (hour := i >> 6) < 12 and (minute := i & 63) < 60:
        #         res.append(f'{hour}:{minute:02d}')

        return res

    def readBinaryWatch1(self, turnedOn: int) -> List[str]:
        """
        分别求出所有可能的时针、分针
        然后拼接
        :param turnedOn:
        :return:
        """
        if turnedOn >= 9:
            return []

        def backTrack(bin1: int, bin0: int, allPosibleRes: List[int], tmpRes: List[str]) -> None:
            """
            根据二进制 0, 1分别的位数总数，得到所有可能表示的数
            :param bin1: 二进制 1 的位数总数
            :param bin0: 二进制 0 的位数总数
            :param allPosibleRes:
            :param tmpRes:
            :return:
            """
            if bin0 == 0 and bin1 == 0:
                allPosibleRes.append(int(''.join(tmpRes), 2))
            if bin0 > 0:
                tmpRes.append('0')
                backTrack(bin1, bin0 - 1, allPosibleRes, tmpRes)
                tmpRes.pop()
            if bin1 > 0:
                tmpRes.append('1')
                backTrack(bin1 - 1, bin0, allPosibleRes, tmpRes)
                tmpRes.pop()

        res = []
        for hourCounts in range(min(3, turnedOn) + 1):
            allPosHours = []
            backTrack(hourCounts, 4 - hourCounts, allPosHours, [])
            allPosMinutes = []
            backTrack(turnedOn - hourCounts, 6 - (turnedOn - hourCounts), allPosMinutes, [])
            # print("---------------------------")
            # print(allPosHours)
            # print(allPosMinutes)
            # # filteredHours = filter(lambda e: e < 12, allPosHours)
            # # filteredHours
            for hour in filter(lambda e: e < 12, allPosHours):
                for minute in filter(lambda e: e < 60, allPosMinutes):
                    res.append(f"{hour}:{minute:02d}")
        return res

    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        return self.readBinaryWatch2(turnedOn)


if __name__ == "__main__":
    turnedOn = 1
    # h, m = 10, 9
    # print(f"{h}:{m:02d}")
    # print(int('1101', 2))
    print(Solution().readBinaryWatch(turnedOn))
